//package _mst;
//
//import java.util.ArrayList;
//import java.util.HashMap;
//import java.util.List;
//import java.util.Map;
//
///**
// * 面试题 08.08. 有重复字符串的排列组合
// */
//public class T0808 {
//    private List<String> ans;
//    private StringBuilder path;
//    private Map<Character, Integer> pathMap;
//    private String S;
//
//    public String[] permutation(String S) {
//        ans = new ArrayList<>();
//        path = new StringBuilder();
//        this.S = S;
//        pathMap = new HashMap<>();
//        for (char c : S.toCharArray()) {
//            pathMap.put(c, pathMap.getOrDefault(c, 0) + 1);
//        }
//        dfs(0);
//        return ans.toArray(new String[0]);
//    }
//
//    private void dfs(int i) {
//        if (i == S.length()) {
//            String string = path.toString();
//            if (!ans.contains(string)) ans.add(string);
//            return;
//        }
//        for (char c : S.toCharArray()) {
//            if (pathMap.containsKey(c) && pathMap.get(c) == 0) continue;
//            path.append(c);
//            pathMap.put(c, pathMap.get(c) - 1);
//            dfs(i + 1);
//            path.deleteCharAt(i);
//            pathMap.put(c, pathMap.get(c) + 1);
//        }
//    }
//}
